//给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
//如果 needle 不是 haystack 的一部分，则返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：haystack = "sadbutsad", needle = "sad"
//输出：0
//解释："sad" 在下标 0 和 6 处匹配。
//第一个匹配项的下标是 0 ，所以返回 0 。
// 
//
// 示例 2： 
//
// 
//输入：haystack = "leetcode", needle = "leeto"
//输出：-1
//解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= haystack.length, needle.length <= 10⁴ 
// haystack 和 needle 仅由小写英文字符组成 
// 
//
// Related Topics 双指针 字符串 字符串匹配 👍 2076 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-11-14 17:49:41
 * @description 28.找出字符串中第一个匹配项的下标
 */
public class FindTheIndexOfTheFirstOccurrenceInAString{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new FindTheIndexOfTheFirstOccurrenceInAString().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int strStr1(String haystack, String needle) {
		for (int i = 0; i < haystack.length(); i++) {
			if (haystack.substring(i, haystack.length()).startsWith(needle))
				return i;
		}
		return -1;
	}

	//kmp写法
	public int strStr(String haystack, String needle) {
		//ss原串 pp匹配串
		if (needle.isEmpty()) return 0;
		//分别读取原串和匹配串长度
		int n = haystack.length(), m = needle.length();
		//加空格，时他们下标从1开始
		haystack = " " + haystack;
		needle = " " + needle;

		char[] s = haystack.toCharArray();
		char[] p = needle.toCharArray();
		//构建next数组，长度为匹配串长度
		int[] next = new int[m + 1];
		//构造过程i=2,j=0开始，i小于等于匹配串长度，
		for (int i = 2, j = 0; i <= m; i++) {
			//匹配不成功j=next[j]
			while (j > 0 && p[i] != p[j + 1]) {
				j = next[j];
			}
			//匹配成功j++
			if (p[i] == p[j + 1]) j++;
			//更新next[i]，结束循环,i++
			next[i] = j;
		}
		//匹配过程，i=1,j=0开始，i小于原串长度
		for (int i = 1, j = 0; i <= n; i++) {
			//匹配不成功j=next[j]
			while (j > 0 && s[i] != p[j + 1]) j = next[j];
			//匹配成功，j++，循环结束后i++
			if (s[i] == p[j + 1]) j++;
			//一整段成功，返回下标
			if (j == m) return i - m;
		}
		return -1;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
